#include <stdio.h>
/*
非稳定排序：值相同元素在经过排序后会改变位置：{49,38,49*,20,97,76},一次划分：{20,38,49*,49,97,76 }
*/
// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数，使用第一个元素作为枢轴
int partition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选择第一个元素作为枢轴
    int i = low + 1;       // i 指向比 pivot 大的第一个元素
    int j = high;          // j 从右边向左扫描

    while (i <= j) {//结束条件：low > high
        // 寻找左侧比 pivot 大的元素
        while (i <= high && arr[i] <= pivot) //结束条件： 左侧元素大于 pivot
        {
            i++;//记录下左侧第一个较大值
        }

        // 寻找右侧比 pivot 小的元素
        while (arr[j] > pivot) {// 结束条件：右侧元素小于 pivot
            j--;//记录下右侧第一个较小的元素
        }

        // 如果 i 仍然小于 j，则交换它们
        if (i < j) {//如果较大的元素在较小的元素左侧，则交换。如果较大元素在较小元素的右侧，则不予交换。等于的情况也不交换
            swap(&arr[i], &arr[j]);//较大元素后移，较小元素前移
        }
    }

    // 将枢轴元素放在正确的位置
    swap(&arr[low], &arr[j]);

    return j;  // 返回枢轴的位置
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 获取分区索引
        int pviotloc = partition(arr, low, high);//从0 到 n-1

        // 递归排序左边部分
        quickSort(arr, low, pviotloc - 1);

        // 递归排序右边部分
        quickSort(arr, pviotloc + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}
